package com.yjh.study.data.structure.question;

import java.util.Arrays;

public class EightQueens {


    /**
     * 八皇后问题
     * 在 8*8 的国标象棋盘上放置 8 个皇后，使任何一个皇后都无法直接吃掉别的皇后
     * 即 同一行，同一列， 同一斜线上都不能出现两个皇后
     * 八皇后问题可以推广为更一般的 n 皇后问题
     */


    public static void main(String[] args) {

        EightQueens eightQueensQuestion = new EightQueens();

        int queensLength = 8;
        int[] arr = new int[queensLength];

        eightQueensQuestion.backTracking(queensLength, 0, arr);
    }

    /**
     * 统计成功放置的次数
     */
    static int count = 0;

    /**
     * @param queensSize 一共几个皇后
     * @param row        在第几行放置皇后
     * @param arr        用数组表示皇后放置的位置，数组下标表示放置的行， 下标对应的元素表示放置的列
     */
    void backTracking(int queensSize, int row, int[] arr) {

        // n 个皇后都按要求放置成功
        if (queensSize == row) {
            count++;
            System.out.println(Arrays.toString(arr) + "count = " + count);
            return;
        }

        // 每行从第 0 列开始尝试放置
        for (int i = 0; i < queensSize; i++) {
            // 放置皇后
            arr[row] = i;

            // 验证是否符合要求; 不符合尝试将皇后放到下一列上
            if (isOk(arr, row)) {
                // 符合要求开始放置下一行的皇后
                backTracking(queensSize, row + 1, arr);
            }
        }
    }

    /**
     * 验证第 row 行放置的皇后是否合适
     *
     * @param arr 表示皇后放置的数组
     * @param row 验证第几行放置的皇后
     * @return true 行,列,斜线都符合要求
     */
    boolean isOk(int[] arr, int row) {

        int col = arr[row];

        for (int i = 0; i < row; i++) {
            if (col == arr[i]) {
                // 列重复
                return false;
            }

            // 斜线重复时, 列的差值 和 行的差值 的绝对值相等
            int rowSpread = row - i;
            int colSpread = col - arr[i];
            if (rowSpread == colSpread || (rowSpread + colSpread == 0)) {
                // 斜线重复
                return false;
            }
        }
        return true;
    }
}
